Peer-to-peer (P2P) systems have been popularized by Internet file-sharing applications, and also have gained significant attention among researchers due to their capability to provide a scalable alternative to more traditional client-server approaches with lower cost.
In peer-to-peer systems based on structured overlays, each peer maintains a routing table that contains a partial list of other peers in the system, such that the routing tables of the peers collectively form an overlay topology. Structured overlays support key-based routing functionality, which means that given a key, the overlay can route the key to a destination defined to host this key. Key-base routing is used to build important distributed data structures, such as distributed hash tables, and to support peer-to-peer applications such as peer-to-peer storage and peer-to-peer multicast applications. The overlay topologies are designed with certain properties so that key-based routings on the topologies are efficient.
Besides routing efficiency, it is also important that the key-base routing implementation also provide a routing consistency guarantee, meaning that the overlay should consistently route the same key to the same destination no matter where the routing is initiated. Routing consistency is important for applications. For example, in a P2P storage application, if the routings are not consistent, a read request to an object may be routed to a wrong destination, causing a read failure or retries or other extra system repair actions. So providing routing consistency can reduce errors and maintenance cost of the applications.
To guarantee routing consistency, we need a correct overlay topology that satisfies the properties as designed. However, maintaining a correct overlay topology is not an easy task because of the highly dynamic natures of P2P systems. Most P2P systems have a large number of peers across wide area networks with unstable connections, and peers join and leave the system at any time, which is referred to as system churn. These dynamic changes of the system may lead to incorrect overlay topologies and cause inconsistent routing results.
Early peer-to-peer system protocols were not good at handling system chum. When the system chum is high, many routings either fail or return inconsistent results or incur long latency due to timeouts and retries. For example, when a large number of peers enter or leave the system at around the same time, which is referred to as flash crowds, the overlay topology could be damaged significantly. Existing proposals do not address this case in detail.
In addition to churns, network failures also cause incorrect overlay topologies. For example, when the IP layer routing failover speed after link failures is very slow, then the recovery from the incorrect overlay topology may also be slow. Moreover, if a backbone link fails and the failover is slow, the network may be partitioned, which may lead to partitions of overlay topologies and inconsistent routing results between different partitioned components.
Moreover, existing peer-to-peer system protocols may lead to an incorrect steady state, called loopy state, which causes inconsistent routing results and cannot be recovered by the basic protocol. A separate loopy detection and removal mechanism may be applied to recover a topology from the loopy state, but the recovery process is O(N) where N is the number of peers in the system. Therefore, the loopy state should be avoided as much as possible.
Overview of Structured P2P Overlays
In a structured P2P overlay, a large circular or linear key space is introduced first and each node chooses a unique key from the key space as its ID. In one example, each node chooses a unique numerical value as its ID and all nodes are sorted in a circular key space of 160 bits.
Nodes in the system can post messages with a destination key drawn from the same key space. The message is routed to a destination node based on the relationship between the destination key and the node ID. In one example, the message will be delivered to the node whose ID is the numerically closest one to the message destination key. In another example, each node owns the zone that starts from its predecessor's ID (exclusive) to its own ID in a circular key space, and the message is routed to the node whose zone contains the message destination key. Such message forwarding behavior based on the destination key is called key-based routing.
Each node in the system maintains a routing table, which contains a subset of nodes to which this node may forward messages for routing purpose. The routing tables on all nodes together form the overlay routing topology, which needs to satisfy certain constraints in order to provide correct and efficient key-based routing in the overlay.
In some implementations, each routing table is divided into two parts: the leafset table 120 and the finger table 130 as shown in FIG. 1. The leafset table remembers the logical neighbors of the node (e.g., node A 110) in the key space, which are the nodes whose IDs are closest to the ID of the node. In one example, the node's leafset table is the union of its predecessor and successor list. In the illustrated example, each node remembers L immediate preceding nodes and L immediate succeeding nodes in its leafset table.
Besides the leafset table, each node also maintains a finger table 130 to improve message routing performance. Different from the leafset table, the finger table remembers nodes that are relatively far away in the ID space. They are selected according to certain criteria to support efficient routing. In one example, the finger table consists of nodes that are 2i distance away in the clockwise distance for different values of i. In another example, a node's finger table is called “routing table” and it remembers nodes that have common prefixes of specific lengths with the local node.
Key-based routing in these overlays typically consists of first routing through the finger tables to forward a message quickly to the neighborhood of the destination, and then routing through the leafset to locate the final destination. Most of the proposals have O(log N) as the routing table size and support O(log N) routing performance, where N is the system scale.
For routing consistency, leafset tables play a key role because they are used to locate the final destination in the process of key-based routing. Furthermore, leafset table maintenance is responsible of detecting node joins and leaves in the system. Therefore, the correctness of the leafset tables is the prerequisite of the routing consistency.
The content of a correct leafset table is determined by the geometry of the key space, the sorting rule of the keys in the key space and the current online nodes in the system. For instance, in a circular key space in which keys are sorted numerically, a node's leafset table must contain node entries with IDs numerically closest to the local node in the key space. Since the key space is circular, leafset tables of all nodes in the system resembles a ring topology.
Enforcing Routing Consistency
Routing consistency in structured P2P overlays is the property ensuring that routings with any given key always reach the correct node mapped by the key (a.k.a. the owner of the key). Unfortunately, most existing protocols only provide best-effort routing and do not guarantee this property. As a result, routings are sometimes erroneous. These routing errors become more frequent when chums and failures drive routing tables of nodes into inconsistent states. Some routing errors are difficult to correct and may exist for a long time.
Routing errors may decrease the performance of KBR-based applications or cause application errors. For example, applications using distributed hash tables to store key-value pairs may falsely report a stored key to be lost when routing to a wrong node, or start unnecessary replication maintenance. It is difficult for individual applications to build complex distributed data structures and systems on top of an inconsistent and error prone routing layer. To a certain extent, this makes structured P2P overlays less competent as a widely applicable building block for distributed systems.